/**
 * XQuery to Scala Translator
 * Fatemeh Borran-Dejnabadi
 * 16 November 2004
 */
// $Id: Parser.scala 10847 2007-04-26 14:16:28Z michelou $

package xquery2src

import java.io._

/** This class implements the parser of the compiler.
 */
class Parser extends Scanner {

  /** Reports an error that a specific token was expected but
   *  a different token found.
   */
  private def error(expected: int): Unit =
    error("token of class " + tokenClass(expected))

  /** Reports an error that a specific token was expected but
   *  a different token found.
   */
  private def error(expected: String) {
    val message:String = "syntax error\n" +
        "expected: " + expected + "\n" +
        "found   : " + representation()
    Report.fail(start, message)
  }

  /** If the current token corresponds to the token class 'expected'
   *  then skip it, otherwise signal an error.
   */
  private def accept(expected: int) =
    if (token == expected)
      nextToken()
    else
      error(expected)

  /** Parse the input and return an abstract syntax tree.
   */
  def parse(): Tree = {
    val result = queryBody()
    accept(EOF)
    result
  }

  /** QueryBody = XMLExpr | Expr
   */
  private def queryBody(): Tree =
    if (token == LTHAN)
      xmlExpr()
    else
      expr()

  /** XMLExpr = "<" ident AttributeList ("/>" | ">" (XMLExpr | ContentExpr) "</" ident ">")
   */
  private def xmlExpr(): XMLExpr = {
    accept(LTHAN)
    val stag: String = chars
    accept(IDENT)
    val attributes: Array[Tree] = attributeList()
    var contents: Tree = null
    if (token == SLASH) {
      accept(SLASH)
      accept(GTHAN)
    }
    else {
      accept(GTHAN);
      if (token == LTHAN)
        contents = xmlExpr();
      else
        contents = contentExpr();
      accept(LTHAN)
      accept(SLASH)
      val etag:String = chars
      if (etag.equals(stag)) {
        accept(IDENT)
        accept(GTHAN)
      }
      else
        error("end-tag is not the same as start-tag!!!")
    }
    new XMLExpr(start, stag, attributes, contents)
  }

  /** AttributeList = AttrExpr*
   */
  private def attributeList(): Array[Tree] = {
    var attributes: List[Tree] = List()
    while (token == IDENT) {
      attributes = attrExpr() :: attributes;
    }
    attributes = attributes.reverse
    var attrArray: Array[Tree] = new Array[Tree](attributes.length)
    attributes.copyToArray(attrArray, 0)
    attrArray
  }

  /** AttrExpr = ident "=" '"' ContentExpr '"'
   */
  private def attrExpr():Tree = {
    val ident:String = chars;
    accept(IDENT);
    accept(EQUAL);
    accept(QUOT);
    val value:Tree = contentExpr();
    accept(QUOT);
    return new AttrExpr(start, ident, value);
  }

  /** ContentExpr = ("{" Expr "}")*
   */
  private def contentExpr(): Tree = {
    var exprs: List[Tree] = List()
    while (token == LACOLAD) {
      accept(LACOLAD)
      exprs = expr() :: exprs
      accept(RACOLAD)
    }
    exprs = exprs.reverse
    var exprsArray: Array[Tree] = new Array[Tree](exprs.length)
    exprs.copyToArray(exprsArray, 0)
    new Expr(start, new Sequence(start, exprsArray))
  }

  /** Expr = ExprSingle ("," ExprSingle)*
   */
  private def expr(): Sequence = {
    var exprs: List[Tree] = List()
    exprs = exprSingle() :: exprs
    while (token == COMMA) {
      accept(COMMA)
      exprs = exprSingle() :: exprs
    }
    exprs = exprs.reverse
    var exprsArray: Array[Tree] = new Array[Tree](exprs.length);
    exprs.copyToArray(exprsArray, 0)
    new Sequence(start, exprsArray)
  }

  /** ExprSingle = FLWORExpr | QuantifiedExpr | IfExpr | OrExpr
   */
  private def exprSingle():Tree = {
    token match {
      case FOR   => return flworExpr();
      case LET   => return flworExpr();
      case SOME  => return quantifiedExpr();
      case EVERY => return quantifiedExpr();
      case IF    => return ifExpr();
      case _     => return orExpr();
    }
  }

  /** FLWORExpr = (ForClause | LetClause)+ WhereClause?
   *               OrderByClause? "return" ExprSingle
   */
  private def flworExpr():Flwor = {
    var forlet:List[Tree] = List();
    if (token == FOR)
      forlet = forClause() :: forlet;
    else if (token == LET)
      forlet = letClause() :: forlet;
    else
      error("FLWORExpr");
    while (token == FOR || token == LET) {
      if (token == FOR)
        forlet = forClause() :: forlet;
      if (token == LET)
        forlet = letClause() :: forlet;
    }
    var wClause:Sequence = null;
    if (token == WHERE)
      wClause = whereClause();
    var oClause:Array[Tree] = null;
    if (token == ORDER)
      oClause = orderByClause();
    accept(RETURN);
    var returnExpr:Tree = null;
    if (token == LTHAN)
      returnExpr = xmlExpr();
    else
      returnExpr = exprSingle();
    forlet = forlet.reverse
    var forletArray: Array[Tree] = new Array[Tree](forlet.length)
    forlet.copyToArray(forletArray, 0)
    new Flwor(start, forletArray, wClause, oClause, returnExpr)
  }

  /** ForClause = "for" "$" Ident "in" ExprSingle
   *               ("," "$" Ident "in" ExprSingle)*
   */
  private def forClause():For = {
    var vars:List[Tree] = List();
    accept(FOR);
    accept(DOLLAR);
    var name:String = chars;
    accept(IDENT);
    accept(IN);
    var domain:Tree = exprSingle();
    var v = new Var(start, name, domain);
    vars = v :: vars;
    while (token == COMMA) {
      accept(COMMA);
      accept(DOLLAR);
      name = chars;
      accept(IDENT);
      accept(IN);
      domain = exprSingle();
      v = new Var(start, name, domain);
      vars = v :: vars;
    }
    vars = vars.reverse
    var varsArray: Array[Tree] = new Array[Tree](vars.length)
    vars.copyToArray(varsArray, 0)
    new For(start, varsArray)
  }

  /** LetClause = "let" "$" Ident ":=" ExprSingle
   *               ("," "$" Ident ":=" ExprSingle)*
   */
  private def letClause():Let = {
    var vars:List[Tree] = List();
    accept(LET);
    accept(DOLLAR);
    var name:String = chars;
    accept(IDENT);
    accept(ASSIGN);
    var domain = exprSingle();
    var v = new Var(start, name, domain);
    vars = v :: vars;
    while (token == COMMA) {
      accept(COMMA);
      accept(DOLLAR);
      name = chars;
      accept(IDENT);
      accept(IN);
      domain = exprSingle();
      v = new Var(start, name, domain);
      vars = v :: vars;
    }
    vars = vars.reverse
    var varsArray: Array[Tree] = new Array[Tree](vars.length)
    vars.copyToArray(varsArray, 0)
    new Let(start, varsArray)
  }

  /** WhereClause = "where" Expr
   */
  private def whereClause(): Sequence = {
    accept(WHERE)
    expr()
  }

  /** OrderByClause = "order" "by" OrderSpec ("," OrderSpec)*
   */
  private def orderByClause():Array[Tree] = {
    var exprs:List[Tree] = List();
    accept(ORDER);
    accept(BY);
    exprs = orderSpec() :: exprs;
    while (token == COMMA) {
      accept(COMMA);
      exprs = orderSpec() :: exprs;
    }
    exprs = exprs.reverse
    var exprsArray: Array[Tree] = new Array[Tree](exprs.length)
    exprs.copyToArray(exprsArray, 0)
    exprsArray
  }

  /** OrderSpec = ExprSingle ("ascending" | "descending")?
   */
  private def orderSpec():OrderBy = {
    val eSingle:Tree = exprSingle();
    var order:String = "";
    if (token == ASCENDING) {
      order = chars;
      accept(ASCENDING);
    }
    else if (token == DESCENDING) {
      order = chars;
      accept(DESCENDING);
    }
    return new OrderBy(start, eSingle, order);
  }

  /** QuantifiedExpr = ("some" "$" | "every" "$") Ident "in" ExprSingle
   *                   ("," "$" Ident "in" ExprSingle)*
   *                   "satisfies" ExprSingle
   */
  private def quantifiedExpr():Tree = {
    var flag:int = 0;
    if (token == SOME) {
      accept(SOME);
      flag = 1;
    }
    else if (token == EVERY) {
      accept(EVERY);
      flag = 2;
    }
    else {
      error("QuantifiedExpr");
      flag = 0;
    }
    accept(DOLLAR);
    var name:String = chars;
    accept(IDENT);
    accept(IN);
    var domain = exprSingle();
    var v = new Var(start, name, domain);
    var vars:List[Tree] = List();
    vars = v :: vars;
    while (token == COMMA) {
      accept(COMMA);
      accept(DOLLAR);
      name = chars;
      accept(IDENT);
      accept(IN);
      domain = exprSingle();
      v = new Var(start, name, domain);
      vars = v :: vars;
    }
    accept(SATISFIES)
    val satisfies = exprSingle()
    vars = vars.reverse
    var varsArray:Array[Tree] = new Array[Tree](vars.length)
    vars.copyToArray(varsArray, 0)
    if (flag == 1) {
      return new Some(start, varsArray, satisfies);
    }
    else if (flag == 2) {
      return new Every(start, varsArray, satisfies);
    }
    else return null;
  }

  /** IfExpr = "if" "(" Expr ")" "then" ExprSingle
   *           "else" ExprSingle
   */
  private def ifExpr():If = {
    accept(IF);
    accept(LPAREN);
    val cond = expr();
    accept(RPAREN);
    accept(THEN);
    val thenIf = exprSingle();
    accept(ELSE);
    val elseIf = exprSingle();
    return new If(start, cond, thenIf, elseIf);
  }

  /** OrExpr = AndExpr ("or" AndExpr)*
   */
  private def orExpr():Tree = {
    var operand1 = andExpr();
    while (token == OR) {
      accept(OR);
      operand1 = new BinOp(start, OR, operand1, andExpr());
    }
    return operand1;
  }

  /** AndExpr = CompExpr ("and" CompExpr)*
   */
  private def andExpr():Tree = {
    var operand1 = compExpr();
    while (token == AND) {
      accept(AND);
      operand1 = new BinOp(start, AND, operand1, compExpr());
    }
    return operand1;
  }

  /** CompExpr = AddExpr (("=" | "!=" | "<" | "<=" | ">" | ">=") AddExpr)?
   */
  private def compExpr():Tree = {
    val operand1 = addExpr();
    if (token == EQUAL || token == NOTEQUAL || token == LTHAN |
        token == LETHAN || token == GTHAN || token == GETHAN) {
	  token match {
            case EQUAL =>
              accept(EQUAL);
              return new BinOp(start, EQUAL, operand1, addExpr());
            case NOTEQUAL =>
              accept(NOTEQUAL);
              return new BinOp(start, NOTEQUAL, operand1, addExpr());
            case LTHAN =>
              accept(LTHAN);
              return new BinOp(start, LTHAN, operand1, addExpr());
            case LETHAN =>
              accept(LETHAN);
              return new BinOp(start, LETHAN, operand1, addExpr());
            case GTHAN =>
              accept(GTHAN);
              return new BinOp(start, GTHAN, operand1, addExpr());
            case GETHAN =>
              accept(GETHAN);
              return new BinOp(start, GETHAN, operand1, addExpr());
            case _ =>
              error("CompExpr");
	  }
    }
    return operand1;
  }

  /** AddExpr = MultExpr (("+" | "-") MultExpr)*
   */
  private def addExpr():Tree = {
    var operand1 = multExpr();
    while (token == PLUS || token == MINUS) {
      if (token == PLUS) {
        accept(PLUS);
        operand1 = new BinOp(start, PLUS, operand1, multExpr());
      }
      else if (token == MINUS) {
        accept(MINUS);
        operand1 = new BinOp(start, MINUS, operand1, multExpr());
      }
      else
        error("AddExpr");
    }
    return operand1;
  }

  /** MultExpr = UnaryExpr (("*" | "div" | "idiv" | "mod") UnaryExpr)*
   */
  private def multExpr():Tree = {
    val operand1 = unaryExpr();
    while (token == TIMES || token == DIV || token == IDIV || token == MOD) {
      token match {
        case TIMES =>
          accept(TIMES); return new BinOp(start, TIMES, operand1, unaryExpr());
        case DIV   =>
          accept(DIV); return new BinOp(start, DIV, operand1, unaryExpr());
        case IDIV  =>
          accept(IDIV); return new BinOp(start, IDIV, operand1, unaryExpr());
        case MOD   =>
          accept(MOD); return new BinOp(start, MOD, operand1, unaryExpr());
	case _     =>
          error("multExpr");
      }
    }
    operand1
  }

  /** UnaryExpr = ("-" | "+")* PathExpr
   */
  private def unaryExpr():Tree = {
    var t:UniOp = null;
    if (token == MINUS || token == PLUS) {
      if (token == MINUS) {
        accept(MINUS);
        t = new UniOp(start, MINUS, unaryExpr());
      }
      else if (token == PLUS) {
        accept(PLUS);
        t = new UniOp(start, PLUS, unaryExpr());
      }
      return t;
    }
    else
      return pathExpr();
  }

  /** PathExpr = ("/" RelPathExpr?)
   *           | ("//" RelPathExpr)
   *           | RelPathExpr
   */
  private def pathExpr():Tree = {
    if (token == SLASH) {
      accept(SLASH);
      return new UniOp(start, SLASH, relPathExpr());
    }
    else if (token == DSLASH) {
      accept(DSLASH);
      return new UniOp(start, DSLASH, relPathExpr());
    }
    else
      return relPathExpr();
  }

  /** RelPathExpr = FilterExpr (("/" | "//") FilterExpr)*
   */
  private def relPathExpr():Tree = {
    var operand1 = filterExpr();
    while (token == SLASH || token == DSLASH) {
      if (token == SLASH) {
        accept(SLASH);
        operand1 = new BinOp(start, SLASH, operand1, filterExpr());
      }
      else if (token == DSLASH) {
        accept(DSLASH);
        operand1 = new BinOp(start, DSLASH, operand1, filterExpr());
      }
    }
    return operand1;
  }

  /** FilterExpr = PrimaryExpr PredicateList
   */
  private def filterExpr():Tree = {
    return new Filter(start, primaryExpr(), predicateList());
  }

  /** PredicateList = ("[" Expr "]")*
   */
  private def predicateList(): Array[Tree] = {
    var predicates: List[Tree] = List()
    while (token == LBRACKET) {
      accept(LBRACKET)
      predicates = expr() :: predicates
      accept(RBRACKET)
    }
    predicates = predicates.reverse
    var predsArray: Array[Tree] = new Array[Tree](predicates.length)
    predicates.copyToArray(predsArray, 0)
    predsArray
  }

  /** PrimaryExpr = Number | String | VarRef | ParenExpr
   *                Ident | FunctionCall
   */
  private def primaryExpr():Tree = {
    var s:String = "";
    token match {
      case NUMBER =>
        s = chars;
        accept(NUMBER);
        return new IntTree(start, Integer.parseInt(s));
      case STRING =>
        s = chars;
        accept(STRING);
        return new StringTree(start, s);
      case IDENT =>
        return functionCall();
      case DOLLAR =>
        accept(DOLLAR);
        s = chars;
        accept(IDENT);
        return new Ident(start, s);
      case ATSIGN =>
        accept(ATSIGN);
        s = chars;
        accept(IDENT);
        return new Attribute(start, s);
      case LPAREN =>
        accept(LPAREN);
        val expr1:Sequence = expr();
        accept(RPAREN);
        return new Expr(start, expr1);
      case LACOLAD =>
        accept(LACOLAD);
        val expr2:Sequence = expr();
        accept(RACOLAD);
        return new Expr(start, expr2);
      case _ =>
        return functionCall();
    }
  }

  /** FunctionCall = BuildinFuncs "(" (ExprSingle ("," ExprSingle)*)? ")"
   */
  private def functionCall():Tree = {
    var op:int = BAD;
    token match {
      case DOC =>
        accept(DOC); op = DOC;
      case DOCUMENT =>
        accept(DOCUMENT); op = DOCUMENT;
      case MIN =>
        accept(MIN); op = MIN;
      case MAX =>
        accept(MAX); op = MAX;
      case COUNT =>
        accept(COUNT); op = COUNT;
      case SUM =>
        accept(SUM); op = SUM;
      case AVG =>
        accept(AVG); op = AVG;
      case NOT =>
        accept(NOT); op = NOT;
      case EMPTY =>
        accept(EMPTY); op = EMPTY;
      case EXISTS =>
        accept(EXISTS); op = EXISTS;
      case DISTINCT =>
        accept(DISTINCT); op = DISTINCT;
      case POSITION =>
        accept(POSITION); op = POSITION;
      case CONTAINS =>
        accept(CONTAINS); op = CONTAINS;
      case STARTSWITH =>
        accept(STARTSWITH); op = STARTSWITH;
      case ENDSWITH =>
        accept(ENDSWITH); op = ENDSWITH;
      case TEXT =>
        accept(TEXT); op = TEXT;
      case _ =>
        val ident:String = chars;
        accept(IDENT);
        return new Element(start, ident);
    }
    var args: List[Tree] = List()
    accept(LPAREN)
    if (token == RPAREN)
      accept(RPAREN);
    else {
      args = exprSingle() :: args
      while (token == COMMA) {
        accept(COMMA)
        args = exprSingle() :: args
      }
      accept(RPAREN)
    }
    args = args.reverse;
    var argsArray: Array[Tree] = new Array[Tree](args.length)
    args.copyToArray(argsArray, 0)
    new FunCall(start, op, argsArray)
  }

}
